home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / qc.cpp < prev    next >
C/C++ Source or Header  |  1992-07-07  |  12KB  |  449 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 2 - QC.CPP: Quadcode support routines
  3. //  Written by:
  4. //    Kenneth Van Camp
  5. //    RR #1 Box 1255
  6. //    East Stroudsburg, PA  18301
  7. //    (717)223-8620
  8. //
  9. //  Functions -
  10. //    QuadCode::FreeMem         free memory from qc
  11. //    QuadCode::QuadCode        constructor from (I,J)
  12. //    QuadCode::Init            initializer from string
  13. //    QuadCode::GetQuit         get val of single quit
  14. //    QuadCode::SetQuit         set val of single quit
  15. //    QuadCode::ToIJ            convert to (I,J) coords
  16. //    QuadCode::Compare         compare two quadcodes
  17. //    QuadCode::Sibling         are two qc's siblings?
  18. //    QuadCode::Contains        does qc contain it?
  19. //    QuadCode::MakeParent      make qc into its parent
  20. //    QuadCode::operator=       assignment operator
  21. //    operator<<                qc "put to" stream
  22. //    operator>>                qc "get from" stream
  23. //
  24. ///////////////////////////////////////////////////////
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include <string.h>
  29. #include <assert.h>
  30. #ifdef __TURBOC__
  31. #include <iostream.h>
  32. #else
  33. #include <stream.hpp>
  34. #endif
  35. #include "qc.h"
  36.   
  37. // The following macro returns the number of bytes reqd
  38. // to store a quadcode, given the number of quits:
  39. #define QC_NBYTES(q)    (((q) - 1) / 4 + 1)
  40.  
  41. // These are shifts & masks to extract a single quit
  42. static int  QCshifts[4] = { 6, 4, 2, 0 };
  43. static int  QCmasks[4]  = { 3<<6, 3<<4, 3<<2, 3 };
  44. // This is the inverse mask:
  45. static int  QCimasks[4] =
  46.     { 0xff^(3<<6), 0xff^(3<<4), 0xff^(3<<2), 0xff^3 };
  47. // And these are masks for each bit in a normal byte:
  48. static int  bitmasks[8] =
  49.     { 1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7 };
  50.  
  51. ///////////////////////////////////////////////////////
  52. // QuadCode::FreeMem: Free dynamic memory.
  53.  
  54. #ifndef STAT_QC
  55. void QuadCode::FreeMem (void)
  56. {
  57.   if (nquits > 0 && qca)
  58.     delete qca;
  59.   qca = NULL;
  60.   nquits = 0;
  61. } // QuadCode::FreeMem
  62. #endif // STAT_QC
  63.  
  64. ///////////////////////////////////////////////////////
  65. // QuadCode::QuadCode: QuadCode constructor from (I,J)
  66. // coordinates of the upper-left corner of the qc.
  67.  
  68. QuadCode::QuadCode (COORD i, COORD j, int nq)
  69. // i      is the vertical row# of quadcode (0 at top)
  70. // j      is the horizontal column# of quadcode
  71. // nq     is the # of quits in quadcode
  72. {
  73. #ifndef STAT_QC
  74.   qca = NULL;
  75. #endif
  76.   nquits = 0;
  77.   assert (nq > 0 && nq <= MAXQUITS);
  78.  
  79.   // We traverse both the (i,j) coordinates and the qc
  80.   // from the msb to the lsb and msq to msq.  Note the
  81.   // following assumes MAXQUITS is a multiple of 8.
  82. #ifdef MSB_FIRST
  83.   BYTE *ip = (BYTE *)&i + (MAXQUITS - nq) / 8;
  84.   BYTE *jp = (BYTE *)&j + (MAXQUITS - nq) / 8;
  85. #else
  86.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1 -
  87.       (MAXQUITS - nq) / 8;
  88.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1 -
  89.       (MAXQUITS - nq) / 8;
  90. #endif
  91.  
  92.   int bit = 7 - (MAXQUITS - nq) % 8;
  93.   int nbytes = QC_NBYTES (nq);
  94. #ifndef STAT_QC
  95.   qca = new BYTE [nbytes];
  96.   assert (qca != NULL);
  97. #endif
  98.  
  99.   memset (qca, '\0', nbytes);
  100.   BYTE  *p = qca;
  101.   nquits = nq;
  102.  
  103.   int   pos = 0;        // position within qc (0,1,2,3)
  104.   for ( ; nq > 0; nq--)
  105.   {
  106.     if (*ip & bitmasks[bit])
  107.       *p |= 1 << (QCshifts[pos] + 1);
  108.     if (*jp & bitmasks[bit])
  109.       *p |= 1 << QCshifts[pos];
  110.     // Advance to next quit
  111.     if (++pos > 3)
  112.     {
  113.       pos = 0;
  114.       p++;
  115.     }
  116.     // Back up to next bit
  117.     if (--bit < 0)
  118.     {
  119.       bit = 7;
  120. #ifdef MSB_FIRST
  121.       ip++;
  122.       jp++;
  123. #else
  124.       ip--;
  125.       jp--;
  126. #endif
  127.     } // if --bit
  128.  
  129.   } // for nq
  130.  
  131. } // QuadCode::QuadCode
  132.  
  133. ///////////////////////////////////////////////////////
  134. // QuadCode::Init: QuadCode initializer from string.
  135.  
  136. void QuadCode::Init (const char *chqc)
  137. // chqc         is the quadcode in a null-terminated
  138. //              character representation - i.e., "123"
  139. {
  140.   int nq = strlen (chqc);
  141. #ifndef STAT_QC
  142.   qca = NULL;
  143. #endif
  144.   nquits = 0;
  145.   assert (nq > 0 && nq <= MAXQUITS);
  146.   size_t nbytes = QC_NBYTES (nq);
  147. #ifndef STAT_QC
  148.   qca = new BYTE [nbytes];
  149.   assert (qca != NULL);
  150. #endif
  151.   memset (qca, '\0', nbytes);
  152.  
  153.   // Store quadcode in binary form, from msq to lsq.
  154.   int  i;
  155.   int  pos; // pos within byte of this quit (0,1,2,3)
  156.   BYTE *p;  // ptr to current byte in qc
  157.   for (i = 0, pos = 0, p = qca; i < nq; i++)
  158.   {
  159.     int val = chqc[i] - '0';
  160.     assert (val >= 0 && val <= 3);
  161.     *p |= val << QCshifts[pos];
  162.     if (++pos > 3)
  163.     {
  164.       pos = 0;
  165.       p++;
  166.     }
  167.   } // for i
  168.  
  169.   nquits = nq;
  170. } // QuadCode::Init
  171.  
  172. ///////////////////////////////////////////////////////
  173. // QuadCode::GetQuit: Return single quit from quadcode.
  174.  
  175. int QuadCode::GetQuit (int quit)
  176. // quit is the pos# of the quit to extract (zero-based).
  177. //      Pos 0 is the high-order quit ('1' in "123").
  178. {
  179.   assert (quit <= nquits && quit >= 0);
  180.  
  181.   int byte = quit / 4;
  182.   int pos = quit % 4;
  183.   return ( (*(qca + byte) & QCmasks[pos]) >>
  184.       QCshifts[pos]);
  185. } // QuadCode::GetQuit
  186.  
  187. ///////////////////////////////////////////////////////
  188. // QuadCode::SetQuit: Set value of a single quit.
  189.  
  190. void QuadCode::SetQuit (int quit, int val)
  191. // quit is the pos# of the quit to extract (zero-based).
  192. // val  is the value of the quit (0, 1, 2 or 3).
  193. {
  194.   assert (quit <= nquits && quit >= 0 && val >= 0 &&
  195.       val < 4);
  196.  
  197.   BYTE *p = qca + quit / 4;
  198.   int pos = quit % 4;
  199.   // Clear out the old value
  200.   *p &= (255 - QCmasks[pos]);
  201.   // Put in the new value
  202.   *p |= val << QCshifts[pos];
  203. } // QuadCode::SetQuit
  204.  
  205. ///////////////////////////////////////////////////////
  206. // QuadCode::ToIJ: Convert the quadcode value to (I,J).
  207. // The offsets returned are the coords of the
  208. // upper-left corner of the quadcode.
  209.  
  210. void QuadCode::ToIJ (COORD &i, COORD &j, int &nq)
  211. // i      is the row#
  212. // j      is the col#
  213. // nq     is the #quits
  214. {
  215.   i = j = nq = 0;
  216.   if (nquits < 1)
  217.     return;
  218.   assert (nquits <= MAXQUITS);
  219.   nq = nquits;
  220.  
  221.   // Go from lsq to msq.  Following loop is based on the
  222.   // conversion algorithm by Gargantini:
  223. #ifdef MSB_FIRST
  224.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1;
  225.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1;
  226. #else
  227.   BYTE *ip = (BYTE *)&i;
  228.   BYTE *jp = (BYTE *)&j;
  229. #endif
  230.   int   quit,       // current quit# in qc
  231.         bit = 0;    // current bit# in byte of (i,j)
  232.  
  233.   for (quit = nquits-1; quit >= 0; quit--)
  234.   {
  235.     int val = GetQuit (quit);
  236.     // Bit pos 0 gives J val, bit pos 1 gives I val.
  237.     int ival = val >> 1;
  238.     int jval = val & 1;
  239.     *ip |= (ival << bit);
  240.     *jp |= (jval << bit);
  241.     // Advance to next bit
  242.     if (bit == 7)
  243.     {
  244.       bit = 0;
  245. #ifdef MSB_FIRST
  246.       ip--;
  247.       jp--;
  248. #else
  249.       ip++;
  250.       jp++;
  251. #endif
  252.     }
  253.     else
  254.       bit++;
  255.   } // for quit
  256.  
  257. } // QuadCode::ToIJ
  258.  
  259. ///////////////////////////////////////////////////////
  260. // QuadCode::Compare: Compare one quadcode to another.
  261. // Return 0 if the two quadcodes are equal; -1 if the
  262. // current quadcode is less than qc; or +1 if the
  263. // current quadcode is greater than qc.
  264.  
  265. int QuadCode::Compare (QuadCode &qc)
  266. // qc         is the quadcode to compare to
  267. {
  268.   // Check for zero-length quadcodes
  269.   if (nquits == 0)
  270.   {
  271.     if (qc.nquits == 0)
  272.       return 0;
  273.     else
  274.       return -1;
  275.   }
  276.   else if (qc.nquits == 0)
  277.     return 1;
  278.  
  279.   BYTE *p1 = qca;
  280.   BYTE *p2 = qc.qca;
  281.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  282.   BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
  283.  
  284.   // Compare each byte of the two quadcodes.
  285.   for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
  286.     if (*p1 != *p2)
  287.     {
  288.       if (*p1 < *p2)
  289.         return -1;
  290.       else
  291.         return 1;
  292.     }
  293.  
  294.   if (nquits == qc.nquits)
  295.     // quadcodes same
  296.     return 0;
  297.   else if (nquits < qc.nquits)
  298.     // this quadcode contains qc
  299.     return -1;
  300.   else
  301.     // qc contains this quadcode
  302.     return 1;
  303. } // QuadCode::Compare
  304.  
  305. ///////////////////////////////////////////////////////
  306. // QuadCode::Sibling: Compare one quadcode to another.
  307. // Return TRUE if they are siblings, FALSE if not.
  308.  
  309. int QuadCode::